#include "BSTMap.h"
#include "FileOperation.h"
#include "AVLTree.h"
#include <iostream>
#include <algorithm>
using namespace std;

template<typename K, typename V>
class HashTable{
private:
	
    int M; // 取模的那个素数，表的长度
    int size; // 表中存储数据的个数
    AVLTree<K, V> *hashTable[];

    int hashCode(K key) {
        std::hash<K> key_hash;
        return key_hash(key);
    }

public:

    HashTable(int M) {
        this->M = M;
        size = 0;
        *hashTable = new AVLTree<K, V>[M];
        for (int i = 0; i < M; ++i) {
            hashTable[i] = new AVLTree<K, V>();
        }
    }

    HashTable() {
        this->M = 97;
        size = 0;
        *hashTable = new AVLTree<K, V>[M];
        for (int i = 0; i < M; ++i) {
            hashTable[i] = new AVLTree<K, V>();
        }
    }
	
	int hash(K key) {
		return (hashCode(key) & 0x7fffffff) % M;
	}
    int getSize() {
        return size;
    }

    void add(K key, V value) {
        AVLTree<K, V> *avlTree = hashTable[hash(key)];
        if (avlTree->contains(key)) {
            avlTree->set(key, value);
        }else {
            avlTree->add(key, value);
            size++;
        }
    }
    V remove(K key) {
        V ret;
        AVLTree<K, V> *avlTree = hashTable[hash(key)];
        if(avlTree->contains(key)){
            ret = avlTree->remove(key);
            size--;
			return ret;
        }else{
			throw "no this key";
		}
    }

    bool contains(K key) {
        return hashTable[hash(key)]->contains(key);
    }

    V get(K key) {
        return hashTable[hash(key)]->get(key);
    }

    void set(K key, V value) {
        AVLTree<K, V> *avlTree = hashTable[hash(key)];
        if (avlTree->contains(key)) {
            avlTree->set(key,value);
        }else{
			avlTree->add(key,value);
			size++;
		}
    }
};

int main(){
   
    HashTable<string,int> *hashT = new HashTable<string,int>();
	 vector<string> words;
	string filename = "pride-and-prejudice.txt";
    if (FileOps::readFile(filename, words)) {
		std::sort(words.begin(),words.end());
        std::cout << "Total words: " << words.size() << std::endl;
        clock_t startTime = clock();
        for (string word : words) {
            if (hashT->contains(word)) {
                hashT->set(word, hashT->get(word) + 1);
            }else{
                hashT->add(word, 1);
            }
        }

        for (string word : words) {
            hashT->contains(word);
        }
        
       clock_t endTime = clock();
	   cout<<"HashTable:"<< double(endTime - startTime) / CLOCKS_PER_SEC << "s"<<endl;
       std::cout << "Total different words: " << hashT->getSize() << std::endl;
       std::cout << "Frequency of PRIDE: " << hashT->get("pride") << std::endl;
       std::cout << "Frequency of PREJUDICE: " << hashT->get("prejudice") << std::endl;

    }

    return 0;
}
